package leetcode_top;
import java.util.*;
import java.util.stream.Collectors;

import org.junit.*;


public class Ex324 {
    class Solution1 {
        public void wiggleSort(int[] nums) {
            dfs(Arrays.stream(nums).boxed().collect(Collectors.toList()), new ArrayList<>(), Integer.MAX_VALUE, false);
            for (int i = 0; i < res.size(); i++) {
                nums[i] = res.get(i);
            }
        }
        List<Integer> res;
        public void dfs(List<Integer> list, List<Integer> cur, int last, boolean big) {
            // if (res != null) return;
            if (list.size() == 0) {
                res = new ArrayList<>(cur);
                return;
            }
            // List<Integer> newList = new ArrayList<>(list);
            int t;
            if (big) {
                for (int i = 0; i < list.size(); i++) {
                    if ((t = list.get(i)) > last) {
                        list.remove(i);
                        cur.add(t);
                        dfs(list, cur, t, !big);
                        cur.remove(cur.size() - 1);
                        list.add(i, t);
                    }
                }
            } else {
                for (int i = 0; i < list.size(); i++) {
                    if ((t = list.get(i)) < last) {
                        list.remove(i);
                        cur.add(t);
                        dfs(list, cur, t, !big);
                        cur.remove(cur.size() - 1);
                        list.add(i, t);
                    }
                }
            }
        }
    }

    class Solution {
        public void wiggleSort2(int[] nums) {
            int len = nums.length;

            //进行快速选择，得到中位数
            // partition(nums, 0, len - 1, len / 2);
            // int mid = nums[len / 2]; //中位数
            int mid = quickSelect(nums, 0, len - 1);

            //利用中位数进行三色国旗问题
            holand(nums, mid);

            //穿插元素，使得数组成波浪型【一正一倒，保证不会相邻相等】
            if (nums.length % 2 == 1) mid++;
           int[] nums1 = new int[mid];
           int[] nums2 = new int[len - mid];
           System.arraycopy(nums, 0, nums1, 0, nums1.length);
           System.arraycopy(nums, mid, nums2, 0, nums2.length);

           for (int i = 0; i < nums1.length; i++) {
               nums[2 * i] = nums1[nums1.length - i - 1];
           }

           
           for (int i = 0; i < nums2.length; i++) {
              nums[2 * i + 1] = nums2[nums2.length - i - 1];
            }
        }

        public void holand(int[] nums, int n) {
            int lo = -1, len = nums.length, hi = len - 1, cur = 0;
            while (cur < hi) { //一旦遍历指针与右边界碰撞，证明已经扫描完
                if (nums[cur] < n) { //小于mid元素，扩张左边界
                    swap(nums, ++lo, cur++);
                } else if (nums[cur] == n) {
                    //等于中间元素，不做任何事
                    //一旦后面有比mid小的时候，真正调换的还是等于区的最左元素
                    cur++;
                } else { //大于mid元素，扩张右边界，这里注意不要移动cur，检查换过来的高位元素
                    swap(nums, cur, hi--);
                }
            }
        }

        //若i大于mid，表示mid的跨度过了中点，可以返回
        public void partition(int[] nums, int lo, int hi, int mid) {
            int i = lo, j = lo;
            int t = nums[hi]; //将尾元素作为参照，扩张小于区的范围
            while (j <= hi) {
                if (nums[j] <= t) {
                    swap(nums, i++, j++);
                } else {
                    j++;
                }
            }
            if (i - 1 > mid) {
                partition(nums, lo, i - 1, mid);
            } else if (i < mid) {
                partition(nums, i, hi, mid);
            }
        }

        public int quickSelect(int[] nums,int left,int right){
            int pivot = nums[left];
            int l = left;
            int r = right;
            while(l<r){
                while(l<r&&nums[r]>=pivot){
                    r--;
                }
                if(l<r){
                    nums[l++]=nums[r];
                }
                while(l<r&&nums[l]<=pivot){
                    l++;
                }
                if(l<r){
                    nums[r--]=nums[l];
                }
            }
            nums[l]=pivot;
            if(l==nums.length/2){
                return l;
            }else if(l>nums.length/2){
                return this.quickSelect(nums,left,l-1);
            }else{
                return this.quickSelect(nums,l+1,right);
            }
        }

        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        //基于桶排序
        public  void wiggleSort(int[] nums) {
            int[] bucket = new int[50000]; //最多五万个数
            int len = nums.length;
            for (int i = 0; i < len; i++) {
                bucket[nums[i]]++;
            }

            int big = len, small = len;
            if (len % 2 == 1) {
                small = len - 1;
                big = len - 2;
            } else {
                small = len - 2;
                big = len - 1;
            }

            for (int i = 0; i < small; i += 2) {
                int j = i;
                while (bucket[j] == 0) {
                    j++;
                }
                nums[i] = j;
                bucket[j]--;
            }

            for (int i = 1; i < big; i += 2) {
                int j = i;
                while (bucket[j] == 0) {
                    j++;
                }
                nums[i] = j;
                bucket[j]--;
            }
            
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,5,1,1,6,4};
        s.wiggleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    @Test
    public void test1() {
        int[] nums = {1,5,1,1,6,4};
        Solution s = new Solution();
        // s.partition(nums, 0, nums.length - 1, nums.length / 2);
        s.quickSelect(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    class Solution2 {
        public  void wiggleSort(int[] nums) {
            int[]bucket=new int[5001];
            for(int num:nums)bucket[num]++;
            int len=nums.length;
            int small,big;//穿插数字时的上界
            //总长度为奇数时，“小 大 小 大 小”边界左右都为较小的数；
            //总长度为偶数时，“小 大 小 大”边界左为较小的数，边界右为较大的数
            if((len&1)==1){
                small=len-1;
                big=len-2;
            }else{
                small=len-2;
                big=len-1;
            }
            int j=5000; //从后往前，将桶中数字穿插到数组中，后界为j
            //桶中大的数字在后面，小的数字在前面，所以先取出较大的数字，再取出较小的数字
            //先将桶中的较大的数字穿插放在nums中
            for(int i=1;i<=big;i+=2){
                while (bucket[j]==0)j--;//找到不为0的桶
                nums[i]=j;
                bucket[j]--;
            }
            //再将桶中的较小的数字穿插放在nums中
            for(int i=0;i<=small;i+=2){
                while (bucket[j]==0)j--;//找到不为0的桶
                nums[i]=j;
                bucket[j]--;
            }
        }
    }
    

}
